package likou.offer;

import java.util.ArrayList;
import java.util.List;

/**
 * @Info:
 * @Author: 唐小尊
 * @Date: 2020/8/17  7:59
 */
public class _34 {
    static List<List<Integer>> daan = new ArrayList<>();


    public static List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) {
            return daan;
        }
        List<Integer> nowLine = new ArrayList<>();
        nowLine.add(root.val);
        caozuo(nowLine, root, sum, root.val);
        return daan;
    }

    public static void caozuo(List<Integer> nowLine, TreeNode nowNode, int sum, int nowSum) {
        if (nowNode.left == null && nowNode.right == null && nowSum == sum) {
            daan.add(nowLine);
        } else {
            if (nowNode.left != null) {
                int leftNowSum = nowSum + nowNode.left.val;
                List<Integer> leftNowLine = new ArrayList<>(nowLine);
                leftNowLine.add(nowNode.left.val);
                caozuo(leftNowLine, nowNode.left, sum, leftNowSum);
            }
            if (nowNode.right != null) {
                int rightNowSum = nowSum + nowNode.right.val;
                List<Integer> rightNowLine = new ArrayList<>(nowLine);
                rightNowLine.add(nowNode.right.val);
                caozuo(rightNowLine, nowNode.right, sum, rightNowSum);
            }
        }
    }


    List<List<Integer>> result;
    List<Integer> col;
    public List<List<Integer>> pathSum2(TreeNode root, int sum) {
        if (root == null) return new ArrayList<>();
        result = new ArrayList<>();
        col = new ArrayList<>();
        dfs(root, sum);
        return result;
    }
    private void dfs(TreeNode node, int num) {
        if (node == null) return;
        num -= node.val;
        col.add(node.val);
        if (num == 0 && node.left == null && node.right == null) result.add(new ArrayList<Integer>(col));
        dfs(node.left, num);
        dfs(node.right, num);
        col.remove(col.size() - 1);
    }

}
